class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 创建虚拟头节点
        ListNode head = new ListNode(-1);
        // 申请三个指针针对后续修改
        ListNode cur1 = l1, cur2 = l2, cur = head;
        // 保存当前两数之和的值
        int sum = 0;
        while (cur1 != null && cur2 != null) {
            // 求和
            sum += cur1.val;
            sum += cur2.val;
            // 构造新节点
            cur.next = new ListNode(sum % 10);
            // 更新 sum cur cur1 cur2 的值
            sum /= 10;
            cur = cur.next;
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        // 可能cur1 != null 也可能 cur2 != null
        while (cur1 != null) {
            // 求和
            sum += cur1.val;
            // 构造新节点
            cur.next = new ListNode(sum % 10);
            // 更新 sum cur cur1
            sum /= 10;
            cur = cur.next;
            cur1 = cur1.next;
        }
        while (cur2 != null) {
            // 求和
            sum += cur2.val;
            // 构造新节点
            cur.next = new ListNode(sum % 10);
            // 更新 sum cur cur2
            sum /= 10;
            cur = cur.next;
            cur2 = cur2.next;
        }
        // 可能还会存在进位
        if (sum != 0) {
            cur.next = new ListNode(sum % 10);
        }
        return head.next;
    }
}

class ListNode {
    int val;
    ListNode next;

    public ListNode() {

    }

    public ListNode(int val) {
        this.val = val;
    }

    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}